\section{Previous work}

In this section, we give an overview of how different free
\commonlisp{} implementations represent and handle method
combinations.  In particular, we compare the technique that each
implementation uses with the three scenarios specified in
\refSec{sec-introduction}.  We do not include commercial \commonlisp{}
implementations, simply because we can not know in detail how the code
is written.  Extensive experimentation might have given sufficient
clues, but we prefer to limit ourselves to implementation where we can
examine the source code.

\subsection{\pcl{}}
\label{sec-pcl}

Portable Common Loops%
\footnote{https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/oop/clos/pcl/0.html},
\pcl{} for short, is a library that implements
the functions defined in the book ``The Art of the Metaobject
Protocol'' \cite{Kiczales:1991:AMP:574212}, and is meant as an add-on
to pre-standard \commonlisp{} implementations, i.e., implementations
without \clos{}.

Most \commonlisp{} implementations that exist today were initially
written before the standard was published, and many of those
implementations chose to use \pcl{} to incorporate \clos{}
functionality, though frequently, the code has since been adapted for
each specific implementation.  Much of the analysis in this section
was also described in \cite{verna.18.els}, although the description in
that paper refers to the way \sbcl{} handled method combinations at
the time that article was written.

\pcl{} unsurprisingly defines the class \texttt{method\--combination}
and then the class \texttt{standard\--method\--combination} as a
subclass of the class named \texttt{method\--combination}.

More surprisingly, it then defines two subclasses of the class
\texttt{standard\--method\--combination}, namely
\texttt{long\--method\-combination} and
\texttt{short\--method\--combination}, each for use with the different
forms (long and short) of the macro
\texttt{define\-method\--combination}.

The class \texttt{standard-method-combination} contains slots for the
method-combination type (i.e., a symbol), and the method-combination
options.

The class \texttt{short-method-combination} adds two more slots:
namely, the operator and a Boolean that indicates whether the operator,
when given a single argument, is the identity function.

The short form of \texttt{define-method-combination} adds a method to
the generic function \texttt{find-method-combination}.  The second
parameter of this method has an \texttt{eql} specializer with the name
of the method-combination type being defined.  The method function of
this method first checks that the options given are valid for the
short form of \texttt{define-method\-combination}, and then it creates
a fresh instance of the class \texttt{short-method-combination}.  In
other words, a fresh method combination is created whenever
\texttt{find-method-combination} is called, which is typically
whenever a generic function is created.  As a result, with a
method-combination type defined by the short form, the method
combination of a generic function using this type is not updated as a
result of redefining that method-combination type, which is undesirable.

Furthermore, \texttt{compute-effective-method} has a method
specialized to the class \texttt{short-method-combination} that
handles the case of the short method combination as a special case.

The long form of \texttt{define-method-combination} turns the body of
the form into a method-combination procedure.  This procedure has the
same lambda list as \texttt{compute-effective\-method}.  The expansion
of the macro stores this procedure in a global hash table, using the
method-combination type as a key.  There is a slot for this procedure
in the class \texttt{long-method-combination}, but this slot is not
used.

Like the short form, the long form also creates a method on
\texttt{find-method-combination}, also with an \texttt{eql}
specializer for the second parameter. This method simply creates an
instance of the class \texttt{long-method-combination}.  The generic
function \texttt{compute-effective-method} has a method specialized to
the class \texttt{long-method-combination}.  This method consults the
hash table to find the method-combination procedure and applies that
procedure to the generic function, the method combination, and the
applicable methods.

Appendix B of \cite{verna.18.els} shows some very strange consequences
of the use of the global hash table, combined with the fact that the
effective-method caches of existing generic functions are not flushed
when the method-combination type is redefined by the long form.  A
generic function may well end up with some effective methods computed
\emph{before} the redefinition and some computed \emph{after} it.
Needless to say, this behavior is very undesirable.

In summary then, the generic function named \texttt{find-method\-combination}
acts as a container for method-combination types, encoded as
\texttt{eql}-specialized methods.  Furthermore, there is no attempt to
reuse existing method combinations.  A new one is created whenever
\texttt{find-method-combination} is called.  Finally, while the
validity of the options is verified for the built-in method
combination types, no such verification is done for custom
method-combination types defined by the long form of
\texttt{define-method-combination}.

\subsection{\sbcl{}}

The \sbcl{}%
\footnote{http://www.sbcl.org/}
\commonlisp{} implementation uses a heavily modified
version of \pcl{} (See \refSec{sec-pcl}).  Prior to April of 2018,
\sbcl{} used the unmodified technique from \pcl{} as described in
\refsec{sec-pcl}.  The technique described in this section is a result
of significant modifications to the code for handling method
combinations.  The article by Didier Verna \cite{verna.18.els}
published at ELS in April of 2018 contained a detailed description of
the technique used by \sbcl{} at that time.  The improvements
to \sbcl{} were likely a result of the descriptions in that article.

One aspect of the \sbcl{} code that remains from the previous version
is that the two subclasses of \texttt{method-combination} are still
present.

An invocation of \texttt{define-method-combination} does not create
any new class.  Instead, an \emph{info} structure is created, and
stored in a hash table that uses the name of the method-combination
type as a key.  This info structure contains a \emph{cache}, which is
an association list.  The key of an element of the association list is
a list of options for the method combination, and the value of an
element is the method-combination object.  Initially, the cache is
empty, except for the info structure associated with the
\texttt{standard} method combination.

The function \texttt{find-method-combination} is given the name of the
method combination and the desired options.  It looks up the
appropriate info structure, and searches the cache for an element
corresponding to the options.  If such an element is found, the
method-combination object is returned.  If no element is found, a new
one is constructed, pushed on the cache, and returned.  The new
element is constructed by consing the list of options and the result
of applying a \emph{constructor function} to the list of options.
This constructor function is stored in a slot in the info structure.
As a result, existing method-combination instances are reused whenever
possible.

When a generic function is defined with one of the built-in method
combinations, or with a method combination defined using the short
form, \sbcl{} will check that the options given to the
\texttt{:method-combination} \texttt{defgeneric} option are valid.
This verification is done by special-purpose code.  However, with a
user-defined method combination using the long form, no verification
is done.  It is only when an attempt is made to invoke the generic
function that the method-combination procedure is invoked, and the
incompatible lambda lists are detected.  Furthermore, the error
message is very general and can be difficult to decipher by the
programmer.

\sbcl{} handles reevaluation of \texttt{define-method-combination}
forms with the name of an existing info entry in the hash table.
Every method-combination instance contains a list of back pointers to
generic functions that use this method combination.  The cache of the
existing info entry is traversed, and for each method combination, the
effective methods of its generic functions are invalidated.
The problems indicated in Appendix B of \cite{verna.18.els} therefore
no longer exist in recent versions of \sbcl{}.  When the
method-combination type is redefined with a different form of
\texttt{define-method-combination}, \sbcl{} correctly changes the
class of the method-combinations of the type in question, but it fails
to verify that the existing options are compatible with the new
definition, even when the redefinition is using the short form of
\texttt{define-method-combination}.  The reason for this failure is
that the options are verified only as a result of a call to
\texttt{find-method-combination}, and this function is not called when
a method-combination type is redefined.

\subsection{\clcl{}}
\label{sec-ccl}

The \clcl{}%
\footnote{https://ccl.clozure.com/}
implementation (\ccl{} for short) defines the class
\texttt{method-combination} and then three subclasses of that class:

\begin{itemize}
\item \texttt{standard-method-combination} with a single instance,
  namely the standard method combination.  This class is used as a
  specializer in a method on the generic function
  \texttt{compute-effective-method} so as to handle the standard
  method combination as a special case.
\item \texttt{short-method-combination} which is used for method
  combinations defined by the short form of the macro
  \texttt{define-method-combination}.
\item \texttt{long-method-combination} which is used for method
  combinations defined by the long form of the macro
  \texttt{define-method-combination}.
\end{itemize}

The class \texttt{standard-method-combination} in \ccl{} thus does not
play the role of a general instantiable subclass of
\texttt{method-combination}.

The generic function \texttt{compute-effective-method} has a method
specialized to each of these subclasses.  The method specialized to
\texttt{standard-method-combination} uses special-purpose code in
order to achieve the effect of the standard method combination.  The
standard method combination is thus not defined using
\texttt{define-method-combination}.  Similarly, the method specialized
to \texttt{short-method-combination} uses special purpose code.  Only
the method specialized to \texttt{long-method-combination} invokes the
method-combination procedure to achieve the desired effect.

In \ccl{}, the macro \texttt{define-method-combination} does not
define a method combination class.  Instead it defines an \emph{info}
vector (disguised as a structure) that acts as a template for creating
method combinations later.  The info vector contains the following
elements:

\begin{itemize}
\item The name of the method-combination class to be created which is
  either \texttt{short-method-combination} or
  \texttt{long-method-combination}.
\item An element that contains the short-form options if the info
  vector was created as a result of the short form of
  \texttt{define-method-combination}, and the method-combination
  procedure (called the \emph{expander function} in \ccl{}) if the
  info vector was created as a result of the long form.
\item A list of \emph{instances}, i.e., method-combination objects that
  share the same info vector.
\item A list of generic functions using method combinations of the
  type defined by the info vector.
\end{itemize}

This information is used in order to invalidate effective-method
caches when a method-combination type is redefined.  Therefore, \ccl{}
does not have the problem that \pcl{} does, described in
\refSec{sec-pcl}.

When a long method-combination type is redefined using the short form
of \texttt{define-method-combination}, every generic function having
a method combination of that type is accessed, and the
method-combination options are checked so that they are valid for the
short method combination, i.e., either there are no explicit options or
the options consist of a singleton list containing either
\texttt{:most-specific-first} or \texttt{:most-specific-last}.  No
analogous verification is made when a short method-combination type is
redefined using the long form.  However, in both cases, the method
combination with the redefined type is passed to
\texttt{change-class}, thereby making the redefinition effective in
all generic functions with a method combination of that type.

\subsection{\ecl{}}
\label{sec-ecl}

The \ecl{}%
\footnote{https://common-lisp.net/project/ecl/}
\commonlisp{} implementation defines the class
\texttt{method-combination}, and method-combination metaobjects are
direct instances of this class.  Thus, in this respect, \ecl{} is not
conforming.

Unlike \pcl{}, \sbcl{}, and \ccl{}, \ecl{} does not define any
subclasses of the instantiable class.  Method-combination types
defined by the short form are rewritten to the equivalent long form.

The macro \texttt{define-method-combination} does not define a new
method-combination class.  Instead it defines a method-combination
procedure.  This procedure computes the effective method of a generic
function.  The lambda list of the method-combination procedure
consists of two required parameters: namely, a generic function and a
list of applicable methods, followed by the lambda list given to
\texttt{define-method\-combination}.  For most built-in
method-combination types, that lambda list will contain an optional
parameter named \texttt{order} with a default value of
\texttt{:most-specific-first}.  The resulting method-combination
procedure is stored in a hash table with the name of the
method-combination type as a key.

When a generic function is created, a new instance of the
\texttt{method-combination} class is created.  The new instance
contains the method-combination procedure and a list of the options
given after the method-combination name in the
\texttt{:method-combination} option to \texttt{defgeneric}.

Redefining a method-combination type does not have any effect on
existing generic functions having a method combination of that type.
The hash table containing method-combination procedures is updated,
but this update does not affect existing generic functions.

The \texttt{standard} method combination is not defined using the
macro \texttt{define-method-combination}.  Instead, it is defined
using special-purpose code.

Incompatibilities between method-combination options given to
\texttt{find-method-combination} and the lambda list of the
method-combination procedure are detected when an effective method
needs to be computed.  Because there is no specific class for method
combinations defined by the short form, this behavior is true also for
method-combination types defined by the short form.

Because the short form is rewritten into the long form, and the body
of the resulting form contains no verification that the option is
either \texttt{:most-specific-first} or \texttt{:most-specific\-last},
it is possible to give any object as an option to
\texttt{find\-method-combination}.  Any object different from the
keyword \texttt{:most-specific-last} will make the resulting method
combination behave as if \texttt{:most-specific-first} had been given.
We argue that this behavior is not conforming, since the description
of the short form of \texttt{define-method-combination} states that
this form ``automatically includes error checking''.

\subsection{\clasp{}}

\clasp{} \cite{Schafmeister:Clasp}
is a \commonlisp{} implementation based on \ecl{} (See
\refSec{sec-ecl}), although all the \clanguage{} code in \ecl{} was
rewritten in \cplusplus{}.

A large part of the \commonlisp{} code in \clasp{} is identical or
near-identical to the corresponding code in \ecl{}, and that includes
the code for handling method combinations.  As a result, \clasp{}
handles method combinations in exactly the same way as \ecl{}.
